package src.tree;

import com.sun.source.tree.Tree;

import java.util.*;

public class Traversal {
    /**
     * 前序遍历递归
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversalRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }

    /**
     * 迭代前序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) return result;

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.addFirst(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pollFirst();
            result.add(node.val);
            if (node.right != null) {
                stack.addFirst(node.right);
            }
            if (node.left != null) {
                stack.addFirst(node.left);
            }
        }
        return result;
    }


    /**
     * 中序遍历递归
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversalRecursive(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        inorder(root, result);
        return result;
    }

    private void inorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }

    /**
     * 迭代中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            if(cur != null) {
                stack.addLast(cur);
                cur = cur.left;
            }else {
                cur = stack.pollLast();
                result.add(cur.val);
                cur = cur.right;
            }
        }

        return result;
    }

    /**
     * 后序遍历递归
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversalRecursive(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);
    }


    /**
     * 迭代后序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;

        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null || !stack.isEmpty()){
            if(cur != null) {
                stack.addLast(cur);
                cur = cur.left;
            }else {
                cur = stack.peekLast();
                if(cur.right !=  null && cur.right != prev) {
                    cur = cur.right;
                }else {
                    stack.removeLast();
                    result.add(cur.val);
                    prev = cur;
                    cur = null;
                }
            }
        }

        return result;
    }

    /**
     * 统一迭代法
     * @param root
     * @return
     */
    public List<Integer> tpreorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) return result;

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.addLast(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.peekLast();
            if (node != null) {
                stack.pollLast(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) stack.addLast(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) stack.addLast(node.left);    // 添加左节点（空节点不入栈）
                stack.addLast(node);                          // 添加中节点
                stack.addLast(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                stack.pollLast();           // 将空节点弹出
                node = stack.peekLast();    // 重新取出栈中元素
                stack.pollLast();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }


    /**
     * 层次遍历
     *
     */
    public static List<List<Integer>> levelOrderTraversal(TreeNode node) {
        List<List<Integer>> resList = new ArrayList<List<Integer>>();

        if (node == null) return resList;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offerLast(node);

        while (!queue.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            for(int len = queue.size(); len > 0; len--){
                TreeNode temp = queue.pollFirst();
                itemList.add(temp.val);

                if (temp.left != null) queue.offerLast(temp.left);
                if (temp.right != null) queue.offerLast(temp.right);
            }
            resList.add(itemList);
        }
        return resList;
    }
}
